package com.example.entity;

import java.util.Stack;

/**
 * @Author: wanqian
 * @Date: 2020/8/4 15:12
 */
public class LinkedListCustom {

    private LinkedNodeCustom head;

    public LinkedNodeCustom getHead() {
        return head;
    }

    public LinkedListCustom() {
        this.head = new LinkedNodeCustom(0, null);
    }

    /**
     * 加在链表末尾
     *
     * @param linkedNode
     */
    public void addNode(LinkedNodeCustom linkedNode) {
        LinkedNodeCustom temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(linkedNode);
    }

    /**
     * 根据id按从小到大排序
     *
     * @param linkedNode
     */
    public void addByOrder(LinkedNodeCustom linkedNode) {
        LinkedNodeCustom temp = head;
        while (temp.getNext() != null) {
            if (temp.getNext().getId() > linkedNode.getId()) {
                break;
            } else if (temp.getNext().getId() == linkedNode.getId()) {
                linkedNode.setNext(temp.getNext().getNext());
                temp.setNext(linkedNode);
                return;
            }
            temp = temp.getNext();
        }
        linkedNode.setNext(temp.getNext());
        temp.setNext(linkedNode);
    }

    public void update(LinkedNodeCustom linkedNode) {
        if (head.getNext() == null) {
            System.out.println("链表为空！");
            return;
        }

        LinkedNodeCustom temp = head;
        while (temp.getNext() != null) {
            if (temp.getNext().getId() == linkedNode.getId()) {
                linkedNode.setNext(temp.getNext().getNext());
                temp.setNext(linkedNode);
                return;
            }
            temp = temp.getNext();
        }
        System.out.println(String.format("未找到id为[%d]的节点", linkedNode.getId()));
    }

    public void delete(int id) {
        LinkedNodeCustom temp = head;
        while (temp.getNext() != null) {
            if (temp.getNext().getId() == id) {
                temp.setNext(temp.getNext().getNext());
                return;
            }
            temp = temp.getNext();
        }
    }

    public void list() {

        LinkedNodeCustom temp = head;
        if (temp.getNext() == null) {
            System.out.println("链表为空");
        }
        while (temp.getNext() != null) {
//            System.out.println(temp.getNext());
//            temp = temp.getNext();

            //先移动指针，避免多进行一次temp.getNext()
            temp = temp.getNext();
            System.out.println(temp.toString());
        }
    }

    public int length() {
        LinkedNodeCustom temp = head;
        if (temp.getNext() == null) {
            System.out.println("链表为空");
        }
        int num = 0;
        while (temp.getNext() != null) {
            num++;
            temp = temp.getNext();
        }
        System.out.println("链表长度为" + num);
        return num;
    }

    /**
     * 获取倒数第n个元素
     *
     * @param lastIndex
     * @return
     */
    public LinkedNodeCustom getFromEnd(int lastIndex) {
        int length = this.length();
        if (lastIndex < 0 || lastIndex > length) {
            System.out.println("无效数字");
            return null;
        }

        //第一个有效节点
        LinkedNodeCustom temp = this.head.getNext();
        //从第一个有效节点开始，向后移动length-lastIndex步
        //例如总长度5，①->②->③->④->⑤。lastIndex为2(即倒数第二个)，则向后移动5-2=3步，
        for (int i = 0; i < length - lastIndex; i++) {
            temp = temp.getNext();
        }
        System.out.println(temp);
        return temp;
    }

    /**
     * 1. 笨方法：先声明一个临时头节点，从当前链表中遍历到尾节点，
     * 然后将该尾节点添加到临时头节点末尾，接着将该节点从原节点断开，循环往复获得一个新的链表。
     * (显而易见，需要轮询size!次，低效！)
     * 2. 好方法：遍历原链表，按顺序将节点插入临时头节点之后即可
     *
     * @return
     */
    public LinkedListCustom reverse() {
        LinkedNodeCustom tempHead = new LinkedNodeCustom(0, null);
        //首个节点
        LinkedNodeCustom temp = this.head.getNext();
        if (temp == null) {
            System.out.println("链表为空");
        }

        while (temp != null) {

            LinkedNodeCustom next = temp.getNext();
            temp.setNext(tempHead.getNext());
            tempHead.setNext(temp);
            temp = next;
        }
        this.head = tempHead;
        return this;
    }

    /**
     * 通过调转指针方向反转链表
     *
     * @return
     */
    public LinkedListCustom reverse2() {

        //首个节点
        LinkedNodeCustom cur = this.head.getNext();
        if (cur == null ) {
            System.out.println("链表为空");
            return this;
        } else if (cur.getNext() == null) {
            System.out.println("链表只有一个节点");
            return this;
        }

        //第二个节点
        LinkedNodeCustom next = cur.getNext();
        //删除首个节点的中包含的指针(反转后为尾节点)
        cur.setNext(null);

        //若存在三个及以上节点
        while (next != null) {
            LinkedNodeCustom next2 = next.getNext();
            next.setNext(cur);
            cur = next;
            next = next2;
        }

        this.head.setNext(cur);

        return this;
    }

    public void reversePrint() {

        //首个节点
        LinkedNodeCustom cur = this.head.getNext();
        if (cur == null ) {
            System.out.println("链表为空");
        } else if (cur.getNext() == null) {
            System.out.println("链表只有一个节点");
        }

        Stack<LinkedNodeCustom> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.getNext();
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
